home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / atre12.zip / LF.ZIP / LF.C < prev    next >
C/C++ Source or Header  |  1991-07-05  |  16KB  |  493 lines
  1. /*****************************************************************************
  2.  ****                                                                     ****
  3.  **** lf.c                                                                ****
  4.  ****                                                                     ****
  5.  **** Copyright (C) A. Dwelly and W.W. Armstrong, 1990.                   ****
  6.  ****                                                                     ****
  7.  **** All rights reserved.                                                ****
  8.  ****                                                                     ****
  9.  **** This is an experimentors package, and demonstration of the adaptive ****
  10.  **** logic network package based on work done by Prof. W. W. Armstrong   ****
  11.  **** and others in the Department of Computing Science, University of    ****
  12.  **** Alberta, and previous work at the Universite de Montreal, and at    ****
  13.  **** AT&T Bell Laboratories, Holmdel, N. J.  The software demonstrates   ****
  14.  **** that networks consisting of many layers of linear threshold         ****
  15.  **** elements can indeed be effectively trained.                         ****
  16.  ****                                                                     ****
  17.  **** License:                                                            ****
  18.  **** A royalty-free license is granted for the use of this software for  ****
  19.  **** NON-COMMERCIAL PURPOSES ONLY. The software may be copied and        ****
  20.  **** modified provided this notice appears in its entirety and unchanged ****
  21.  **** in all copies, whether changed or not.  Persons modifying the code  ****
  22.  **** are requested to state the date, the changes made and who made them ****
  23.  **** in the modification history.                                        ****
  24.  ****                                                                     ****
  25.  **** Warranty:                                                           ****
  26.  **** No warranty of any kind is provided with this software.             ****
  27.  **** This software is not supported.  Neither the authors, nor the       ****
  28.  **** University of Alberta, its officers, agents, servants or employees  ****
  29.  **** shall be liable or responsible in any way for any damage to         ****
  30.  **** property or direct personal or consequential injury of any nature   ****
  31.  **** whatsoever that may be suffered or sustained by any licensee, user  ****
  32.  **** or any other party as a consequence of the use or disposition of    ****
  33.  **** this software.                                                      ****
  34.  ****                                                                     ****
  35.  **** Patent:                                                             ****
  36.  **** The use of a digital circuit which transmits a signal indicating    ****
  37.  **** heuristic responsibility is protected by U. S. Patent 3,934,231     ****
  38.  **** and others assigned to Dendronic Decisions Limited of Edmonton,     ****
  39.  **** W. W. Armstrong, President.                                         ****
  40.  ****                                                                     ****
  41.  **** A royalty-free license is granted for the use of this patent to     ****
  42.  **** run this software for NON-COMMERCIAL PURPOSES ONLY and the          ****
  43.  **** extension of this patent license to modified versions of this       ****
  44.  **** software is granted provided the purpose is NON-COMMERCIAL ONLY.    ****
  45.  ****                                                                     ****
  46.  **** Modification history:                                               ****
  47.  ****                                                                     ****
  48.  **** 90.09.05 Initial implementation, A.Dwelly                           ****
  49.  **** 91.04.15 Port to PC and minor bug fixes, R. Manderscheid            ****
  50.  **** 91.05.20 Windows Port & Windows Extensions, M. Thomas               ****
  51.  ****                                                                     ****
  52.  *****************************************************************************/
  53.  
  54. #include <stdio.h>
  55. #include <math.h>
  56. #include <stdlib.h>
  57. #include <windows.h>
  58. #include "atree.h"
  59. #include "lf.h"
  60.  
  61. #define Printf(str,fmt1,fmt2) sprintf(szBuffer,str,fmt1,fmt2)
  62.  
  63. #define VERBOSITY 0
  64. #define CORRECTION_FACTOR 10000
  65. #define CODOMAIN (prog.dimensions - 1)
  66.  
  67. prog_type prog;
  68.  
  69. LPBIT_VEC domain_set;
  70. LPBIT_VEC codomain_set;
  71. LPATREE far * far *forest;
  72.  
  73. extern FILE *yyin;
  74. extern int line_no;
  75. extern bool test_size_flag;
  76. extern bool train_size_flag;
  77. extern bool largest_flag;
  78. extern bool smallest_flag;
  79.  
  80. void NEAR PASCAL
  81. prog_init()
  82. {
  83.     atree_init();
  84.     train_size_flag = FALSE;
  85.     test_size_flag = FALSE;
  86.     largest_flag = FALSE;
  87.     smallest_flag = FALSE;
  88.     prog.vote = 1;
  89. }
  90.  
  91. void NEAR PASCAL
  92. read_prog(fp)
  93.  
  94. FILE *fp;
  95.  
  96. {
  97.     yyin = fp;
  98.     line_no = 1;
  99.  
  100.     if (yyparse() == -1)
  101.         prog.error = TRUE;
  102. }
  103.  
  104. BOOL NEAR PASCAL
  105. process_prog(HWND hwnd)
  106.  
  107. {
  108.     int i;
  109.     int j;
  110.     int nv;
  111.     LPBIT_VEC far *concat;
  112.     LPBIT_VEC bool_res;
  113.  
  114.     /*
  115.      * When this function is called, the program has been read in, and
  116.      * the relevant details have been stored in the global structure
  117.      * 'prog'. We have some semantic processing to do, then the trees
  118.      * can be trained as specified.
  119.      */
  120.  
  121.     /* Quantize the dimensions */
  122.  
  123.     prog.width_sum = 0;
  124.     domain_set = (LPBIT_VEC) WinMem_Malloc(LMEM_MOVEABLE, (unsigned) sizeof(bit_vec) *
  125.                                     prog.trainset_sz);
  126.     MEMCHECK(domain_set);
  127.     codomain_set = (LPBIT_VEC) WinMem_Malloc(LMEM_MOVEABLE, (unsigned) sizeof(bit_vec) *
  128.                                       prog.trainset_sz);
  129.     MEMCHECK(codomain_set);
  130.  
  131.     for (i = 0; i < prog.dimensions; i++)
  132.     {
  133.         if (!largest_flag)
  134.         {
  135.             prog.largest[i] = prog.train_table[i][0];
  136.  
  137.             for (j = 1; j < prog.trainset_sz; j++)
  138.             {
  139.                 if (prog.train_table[i][j] > prog.largest[i])
  140.                 {
  141.                     prog.largest[i] = prog.train_table[i][j];
  142.                 }
  143.             }
  144.  
  145.             for (j = 1; j < prog.testset_sz; j++)
  146.             {
  147.                 if (prog.test_table[i][j] > prog.largest[i])
  148.                 {
  149.                     prog.largest[i] = prog.test_table[i][j];
  150.                 }
  151.             }
  152.         }
  153.         if (!smallest_flag)
  154.         {
  155.             prog.smallest[i] = prog.train_table[i][0];
  156.  
  157.             for (j = 1; j < prog.trainset_sz; j++)
  158.             {
  159.                 if (prog.train_table[i][j] < prog.smallest[i])
  160.                 {
  161.                     prog.smallest[i] = prog.train_table[i][j];
  162.                 }
  163.             }
  164.  
  165.             for (j = 1; j < prog.testset_sz; j++)
  166.             {
  167.                 if (prog.test_table[i][j] < prog.smallest[i])
  168.                 {
  169.                     prog.smallest[i] = prog.test_table[i][j];
  170.                 }
  171.             }
  172.         }
  173.  
  174.         /* Check for constant columns */
  175.  
  176.         if (prog.largest[i] == prog.smallest[i])
  177.         {
  178.             char szBuffer[80];
  179.             wsprintf(szBuffer,"Semantics error: column %d of function definition is a constant",i);
  180.             MessageBox(hwnd, szBuffer, "LF ERROR", MB_OK);
  181.             return(FALSE);
  182.         }
  183.  
  184.         /* Correct largest value */
  185.  
  186.         if (prog.string_width[i] > 1)
  187.         {
  188.             prog.largest[i] += 1/(CORRECTION_FACTOR * prog.quant[i]);
  189.         }
  190.  
  191.         /* prog.width_sum is the bit width of the domain of the function */
  192.  
  193.         if (i < CODOMAIN)
  194.         {
  195.             prog.width_sum += prog.string_width[i];
  196.         }
  197.  
  198.         prog.quant_step[i] = (prog.largest[i] - prog.smallest[i])/
  199.                               prog.quant[i];
  200.  
  201.         if (prog.string_width[i] > 1)
  202.         {
  203.             prog.random_walk[i] = atree_rand_walk(prog.quant[i] + 1,
  204.                                                   prog.string_width[i],
  205.                                                   prog.walk_step[i]);
  206.         }
  207.         else
  208.         {
  209.             /* one of the columns is boolean */
  210.  
  211.             prog.random_walk[i] = NULL;
  212.         }
  213.     } /* for (i...) */
  214.  
  215.     /*
  216.      * random_walk[i] covers the dimension i.
  217.      * we now create the training set of bit vectors.
  218.      */
  219.  
  220.      concat = (LPBIT_VEC far *) WinMem_Malloc(LMEM_MOVEABLE, (unsigned)(CODOMAIN) * sizeof(LPBIT_VEC));
  221.      MEMCHECK(concat);
  222.  
  223.      for (i = 0; i < prog.trainset_sz; i++)
  224.      {
  225.          for (j = 0; j < CODOMAIN; j++)
  226.          {
  227.              if (prog.string_width[j] > 1)
  228.              {
  229.                  nv =  (int)floor((prog.train_table[j][i] - prog.smallest[j])/
  230.                                    prog.quant_step[j]);
  231.                  concat[j] = prog.random_walk[j] + nv;
  232.              }
  233.              else
  234.              {
  235.                  /* boolean data */
  236.  
  237.                  bool_res = bv_create(1);
  238.                  bv_set(0,bool_res,prog.train_table[j][i] != 0);
  239.                  concat[j] = bool_res;
  240.              }
  241.         }
  242.         domain_set[i] = *(bv_concat(CODOMAIN, concat));
  243.      }
  244.      /* And the codomain set */
  245.      for (i = 0; i < prog.trainset_sz; i++)
  246.      {
  247.          if (prog.string_width[CODOMAIN] > 1)
  248.          {
  249.              nv = (int) floor((prog.train_table[CODOMAIN][i] - 
  250.                                prog.smallest[CODOMAIN])/
  251.                                prog.quant_step[CODOMAIN]);
  252.              codomain_set[i] = prog.random_walk[prog.dimensions -1][nv];
  253.          }
  254.          else
  255.          {
  256.              bool_res = bv_create(1);
  257.              bv_set(0,bool_res,prog.train_table[CODOMAIN][i] != 0);
  258.              codomain_set[i] = *bool_res;
  259.          }
  260.      }
  261.  
  262.  
  263.     /* 
  264.      * For each tree (the number of bits in the ranges bit_string -
  265.      * create a tree and train it.
  266.      */
  267.  
  268.     forest = (LPATREE far * far *) WinMem_Malloc(LMEM_MOVEABLE, (unsigned) sizeof(LPATREE far *) *
  269.                               prog.string_width[CODOMAIN]);
  270.     MEMCHECK(forest);
  271.  
  272.     for (i = 0; i < prog.string_width[CODOMAIN]; i++)
  273.     {
  274.         forest[i] = (LPATREE far *) WinMem_Malloc(LMEM_MOVEABLE, (unsigned) sizeof(LPATREE) * prog.vote);
  275.         MEMCHECK(forest[i]);
  276.     }
  277.  
  278.     /* parallelism here ? */
  279.  
  280.     for (i = 0; i < prog.string_width[CODOMAIN]; i++)
  281.     {
  282.         for (j = 0; j < prog.vote; j++)
  283.         {
  284.             forest[i][j] = atree_create(prog.width_sum,prog.tree_sz);
  285.             (void) atree_train(forest[i][j],domain_set, codomain_set,
  286.                                i, prog.trainset_sz, prog.max_correct,
  287.                                prog.max_epochs, VERBOSITY);
  288.         }
  289.     }
  290.  
  291.     return(TRUE);
  292. }
  293.  
  294.  
  295. void NEAR PASCAL
  296. test_prog(HWND hwnd, LPSTR szOutFile)
  297.  
  298. {
  299.     /* Test the forest against the test set */
  300.  
  301.     int i;
  302.     int j;
  303.     int k;
  304.     LPBIT_VEC result;
  305.     LPBIT_VEC far *concat;
  306.     int nv;
  307.     LPBIT_VEC test_vec;
  308.     int cl;
  309.     int closest;
  310.     int closest_bit_diff;
  311.     int weight;
  312.     LPBIT_VEC bool_res;
  313.     int hOut;                   /* file Handle */
  314.     char szBuffer[80];
  315.  
  316.     /* Create room for the results */
  317.  
  318.     result = (LPBIT_VEC )WinMem_Malloc(LMEM_MOVEABLE,(unsigned)sizeof(bit_vec)*prog.testset_sz);
  319.     MEMCHECK(result);
  320.  
  321.     test_vec = (LPBIT_VEC )WinMem_Malloc(LMEM_MOVEABLE,(unsigned)sizeof(bit_vec)*prog.testset_sz);
  322.     MEMCHECK(test_vec);
  323.  
  324.     for (i = 0; i < prog.testset_sz; i++)
  325.     {
  326.         result[i] = *(bv_create(prog.string_width[CODOMAIN]));
  327.     }
  328.  
  329.     /* Create test set inputs */
  330.  
  331.     concat = (LPBIT_VEC far *) WinMem_Malloc(LMEM_MOVEABLE,(unsigned)(CODOMAIN) *
  332.                                   sizeof(LPBIT_VEC ));
  333.     MEMCHECK(concat);
  334.     for (i = 0; i < prog.testset_sz; i++)
  335.     {
  336.         for (j = 0; j < CODOMAIN; j++)
  337.         {
  338.             if (prog.string_width[j] > 1)
  339.             {
  340.                 nv = (int)floor((prog.test_table[j][i] - prog.smallest[j])/
  341.                                 prog.quant_step[j]);
  342.                 prog.test_table_quant[j][i] = nv;
  343.                 concat[j] = prog.random_walk[j] + nv;
  344.             }
  345.             else
  346.             {
  347.                 bool_res = bv_create(1);
  348.                 bv_set(0,bool_res,prog.test_table[j][i] != 0);
  349.                 concat[j] = bool_res;
  350.             }
  351.         }
  352.         test_vec[i] = *(bv_concat(CODOMAIN, concat));
  353.  
  354.         nv = (int)floor((prog.test_table[CODOMAIN][i] -
  355.         prog.smallest[CODOMAIN])/ prog.quant_step[CODOMAIN ]);
  356.         prog.test_table_quant[CODOMAIN][i] = nv;
  357.     }
  358.  
  359.     /* Now test each tree in turn */
  360.  
  361.    for (i = 0; i < prog.string_width[CODOMAIN]; i++)
  362.    {
  363.        for (j = 0; j < prog.testset_sz; j++)
  364.        {
  365.            weight = 0;
  366.            for (k = 0; k < prog.vote; k++)
  367.            {
  368.                if (atree_eval(forest[i][k], test_vec + j))
  369.                {
  370.                    weight++;
  371.                }
  372.                bv_set(i,result + j, weight > (prog.vote / 2));
  373.            }
  374.        }
  375.    }
  376.  
  377.    /* Now calculate the nearest vector in the codomains random walk */
  378.  
  379.    /* open output file */
  380.  
  381.    if ((hOut = _lcreat(szOutFile, 0)) == -1)
  382.        {
  383.        wsprintf(szBuffer,"Cannot open %s ", szOutFile);
  384.        MessageBox(hwnd, szBuffer, "LF File Error", MB_OK);
  385.        return;
  386.        }
  387.  
  388.    if (prog.string_width[CODOMAIN] > 1)
  389.    {
  390.        for (i = 0; i < prog.testset_sz; i++)
  391.        {
  392.             closest_bit_diff = prog.string_width[CODOMAIN];
  393.             closest = 0;
  394.             for (j = 0; j < prog.quant[CODOMAIN]; j++)
  395.             {
  396.                 if ((cl = bv_diff(result + i,prog.random_walk[CODOMAIN] + j)) < closest_bit_diff)
  397.                 {
  398.                     closest_bit_diff = cl;
  399.                     closest = j;
  400.                 }
  401.             }
  402.  
  403.             for (j = 0; j < prog.dimensions; j++)
  404.             {
  405.                 Printf("%f %d \t",prog.test_table[j][i],prog.test_table_quant[j][i]);
  406.                 _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  407.             }
  408.             Printf("%f %d \r\n",(closest * prog.quant_step[CODOMAIN]) + prog.smallest[CODOMAIN],closest);
  409.                 _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  410.        }
  411.    }
  412.    else
  413.    {
  414.        for (i = 0; i < prog.testset_sz; i++)
  415.        {
  416.            for (j = 0; j < prog.dimensions; j++)
  417.            {
  418.                Printf("%f %d \t",prog.test_table[j][i],prog.test_table_quant[j][i]);
  419.                _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  420.            }
  421.            Printf("%f %d \r\n",(float) bv_extract(0,result + i),bv_extract(0,result + i));
  422.                 _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  423.         }
  424.    }
  425.  
  426.    _lclose((int)hOut);       /* close output file */
  427. }
  428.  
  429.  
  430. BOOL NEAR PASCAL
  431. main(HWND hwnd, LPSTR szInFile, LPSTR szOutFile)
  432.  
  433. {
  434.     FILE *fp;
  435.     PSTR szFileName;
  436.  
  437.     /* Initialise the default values for the program */
  438.  
  439.     prog_init();
  440.  
  441.     if (szInFile == NULL)
  442.     {
  443.         MessageBox(hwnd, "No Input File Specified", "LF File Error", MB_OK);
  444.         return(FALSE);
  445.     }
  446.     if (szOutFile == NULL)
  447.     {
  448.         MessageBox(hwnd, "No Output File Specified", "LF File Error", MB_OK);
  449.         return(0);
  450.     }
  451.  
  452.     /* Read the input file */
  453.  
  454.     lstrcpy((LPSTR)szFileName, szInFile);   /* fopen needs near pointer */
  455.     
  456.     if ((fp = fopen(szFileName,"r")) == NULL)
  457.     {
  458.         char szBuffer[80];
  459.         wsprintf(szBuffer,"Can't open %s ", szInFile);
  460.         MessageBox(NULL, szBuffer, "LF File Error", MB_OK);
  461.         return (FALSE);
  462.     }
  463.     else
  464.     {
  465.         read_prog(fp);
  466.         (void) fclose(fp);
  467.     }
  468.  
  469.     /* Train the trees as specified if there were no syntax errors */
  470.  
  471.     if (!prog.error)
  472.     {
  473.  
  474.         MessageBox(hwnd, "Processing program", "LF", MB_OK);
  475.         if(!process_prog(hwnd))
  476.             {
  477.             return(FALSE);
  478.             }
  479.     }
  480.  
  481.     /* Execute the trees as specified */
  482.  
  483.     if (!prog.error)
  484.     {
  485.         MessageBox(hwnd, "Testing program", "LF", MB_OK);
  486.         test_prog(hwnd, szOutFile);
  487.     }
  488.  
  489.     /* Finish */
  490.  
  491.     return(TRUE);
  492. }
  493.